use std::cmp::Ordering;
use std::mem::{swap, zeroed};
use std::ptr::{null_mut, write, NonNull};

use crate::collections::common::{
    copy_from_slice, delete_at_slice, insert_at_slice, swap_in_slice_at, swap_slices,
    SearchTreeBase,
};

struct BTreeNode<K, V, const N: usize> {
    n_keys: usize,
    keys: [K; N],   // because of the lack of the evaluatable checked in const generics,
    values: [V; N], // [Type; N - 1] is not supported currently.
    parent: Option<NonNull<BTreeNode<K, V, N>>>,
    children: [Option<NonNull<BTreeNode<K, V, N>>>; N],
}

impl<K, V, const N: usize> BTreeNode<K, V, N>
where
    K: Copy + Ord + Default,
    V: Clone + Sized,
{
    #[inline]
    pub fn posit(&self, key: &K) -> usize {
        let (mut i, mut j) = (0, self.n_keys);
        while i != j {
            match self.keys[(i + j) / 2].cmp(key) {
                Ordering::Less => i = (i + j) / 2 + 1,
                Ordering::Equal => return (i + j) / 2,
                Ordering::Greater => j = (i + j) / 2,
            }
        }
        i
    }

    #[inline]
    pub fn index(&self, child: NonNull<Self>) -> Option<usize> {
        self.children
            .iter()
            .enumerate()
            .find_map(|(idx, &c)| match c {
                Some(c) if c == child => Some(idx),
                _ => None,
            })
    }

    #[inline]
    pub fn create() -> Box<Self> {
        Box::new(Self {
            n_keys: 0,
            keys: [Default::default(); N],
            values: unsafe { zeroed() },
            parent: None,
            children: [None; N],
        })
    }

    #[inline]
    pub fn try_insert_is_full(&mut self, key: K, val: V) -> bool {
        let place = self.posit(&key);
        assert!(!self.keys[place].eq(&key), "key exists already");
        unsafe {
            insert_at_slice(&mut self.keys, key, place, self.n_keys);
            insert_at_slice(&mut self.values, val, place, self.n_keys);
        }
        self.n_keys += 1;
        self.n_keys == N
    }

    #[inline]
    pub fn try_delete_min_size(&mut self, idx: usize) -> bool {
        unsafe {
            delete_at_slice(&mut self.keys, idx, self.n_keys);
            delete_at_slice(&mut self.values, idx, self.n_keys);
        }
        self.n_keys -= 1;
        self.n_keys < (N - 1) / 2
    }

    #[inline]
    pub fn is_leaf(&self) -> bool {
        self.children[0].is_none()
    }
}

#[derive(Clone)]
pub struct BTree<K, V, const N: usize> {
    size: usize,
    root: NonNull<BTreeNode<K, V, N>>,
}

impl<K, V, const N: usize> SearchTreeBase<K, V> for BTree<K, V, N>
where
    K: Copy + Ord + Default,
    V: Clone + Sized,
{
    #[inline]
    fn new() -> Self {
        Self {
            size: 0,
            root: Box::leak(BTreeNode::create()).into(),
        }
    }

    #[inline]
    fn insert(&mut self, key: K, val: V) -> bool {
        unsafe {
            let (mut node, mut idx) = (self.root.as_ptr(), 0);
            let (mut k, mut v) = (key, val);
            while !(*node).is_leaf() {
                idx = (*node).posit(&key);
                if (*node).keys[idx].eq(&key) {
                    return false;
                }
                if let Some(n) = (*node).children[idx] {
                    node = n.as_ptr();
                }
            }
            let try_idx = (*node).posit(&key);
            if (*node).keys[try_idx].eq(&key) {
                return false;
            }
            let mut leaves: Vec<Option<NonNull<BTreeNode<K, V, N>>>> = vec![None; N + 1];
            while (*node).try_insert_is_full(k, v) {
                (*node).n_keys = N / 2;
                k = (*node).keys[N / 2];
                v = (*node).values[N / 2].clone();
                let brother: NonNull<BTreeNode<K, V, N>> = Box::leak(BTreeNode::create()).into();
                let n_keys = (N - 1) / 2;
                (*brother.as_ptr()).n_keys = n_keys;
                copy_from_slice(
                    &mut (*node).keys[N / 2 + 1..],
                    &mut (*brother.as_ptr()).keys,
                    n_keys,
                );
                copy_from_slice(
                    &mut (*node).values[N / 2 + 1..],
                    &mut (*brother.as_ptr()).values,
                    n_keys,
                );
                if !leaves[0].is_none() {
                    swap_slices(&mut (*node).children, &mut leaves, N / 2 + 1);
                    swap_slices(
                        &mut (*brother.as_ptr()).children,
                        &mut leaves[N / 2 + 1..],
                        n_keys + 1,
                    );
                    for c in (*brother.as_ptr()).children.iter() {
                        if let &Some(x) = c {
                            (*x.as_ptr()).parent = Some(brother);
                        }
                    }
                }

                if let Some(parent) = (*node).parent {
                    (*brother.as_ptr()).parent = Some(parent);
                    swap_slices(&mut (*parent.as_ptr()).children, &mut leaves, N);
                    insert_at_slice(&mut leaves, Some(brother), idx + 1, N);
                    node = parent.as_ptr();
                } else {
                    let parent = Box::leak(BTreeNode::create()).into();
                    (*node).parent = Some(parent);
                    (*brother.as_ptr()).parent = Some(parent);
                    leaves[0] = Some(self.root);
                    leaves[1] = Some(brother);
                    self.root = parent;
                    node = parent.as_ptr();
                }
            }
            copy_from_slice(&mut leaves, &mut (*node).children, (*node).n_keys + 1);
            self.size += 1;
            return true;
        }
    }

    #[inline]
    fn delete(&mut self, key: K) -> bool {
        unsafe {
            let mut key = key;
            let mut node = self.root.as_ptr();
            let mut idx = (*node).posit(&key);
            while !(*node).keys[idx].eq(&key) {
                if let Some(n) = (*node).children[idx] {
                    node = n.as_ptr();
                    idx = (*node).posit(&key);
                } else {
                    return false;
                }
            }

            if let Some(child) = (*node).children[idx] {
                let mut child = child.as_ptr();
                while let Some(c) = (*child).children[(*child).n_keys] {
                    child = c.as_ptr();
                }
                let c_idx = (*child).n_keys - 1;
                key = (*child).keys[c_idx];
                (*child).keys[c_idx] = (*node).keys[idx];
                write(
                    (*child).values.as_mut_ptr().add(c_idx),
                    (*node).values[idx].clone(),
                );
                node = child;
                idx = c_idx;
            }

            while (*node).try_delete_min_size(idx) {
                if let Some(parent) = (*node).parent {
                    let parent = parent.as_ptr();
                    idx = (*parent).posit(&key);
                    let (lnode, rnode) = match idx {
                        0 => (None, (*parent).children[idx + 1]),
                        n if n == N => ((*parent).children[idx - 1], None),
                        _ => ((*parent).children[idx - 1], (*parent).children[idx + 1]),
                    };

                    let (brother, par_idx, bro_idx, chd_idx) = match (lnode, rnode) {
                        // right brother has enough keys
                        (_, Some(ptr)) if (*ptr.as_ptr()).n_keys > (N - 1) / 2 => {
                            (ptr.as_ptr(), idx, 0, 0)
                        }
                        // left brother has enough keys
                        (Some(ptr), _) if (*ptr.as_ptr()).n_keys > (N - 1) / 2 => (
                            ptr.as_ptr(),
                            idx - 1,
                            (*ptr.as_ptr()).n_keys - 1,
                            (*ptr.as_ptr()).n_keys,
                        ),
                        _ => (null_mut(), 0, 0, 0),
                    };

                    if !brother.is_null() {
                        let (key, val) =
                            ((*parent).keys[par_idx], (*parent).values[par_idx].clone());
                        (*node).try_insert_is_full(key, val);
                        (*parent).keys[par_idx] = (*brother).keys[bro_idx];
                        write(
                            (*parent).values.as_mut_ptr().add(par_idx),
                            (*brother).values[bro_idx].clone(),
                        );
                        if !(*brother).is_leaf() {
                            let child = (*brother).children[chd_idx];
                            (*node).children[(*node).n_keys] = child;
                            (*child.unwrap().as_ptr()).parent = (*parent).children[idx];
                            delete_at_slice(
                                &mut (*brother).children,
                                chd_idx,
                                (*brother).n_keys + 1,
                            );
                        }
                        (*brother).try_delete_min_size(bro_idx);
                        break;
                    } else {
                        // combines
                        let (centre, pnode) = match rnode {
                            Some(ptr) => (node, ptr.as_ptr()),
                            None => (lnode.unwrap().as_ptr(), node),
                        };
                        let (key, val) =
                            ((*parent).keys[par_idx], (*parent).values[par_idx].clone());
                        (*centre).try_insert_is_full(key, val);
                        let (n_centre, n_node) = ((*centre).n_keys, (*pnode).n_keys);
                        copy_from_slice(
                            &mut (*pnode).keys,
                            &mut (*centre).keys[n_centre..],
                            n_node,
                        );
                        copy_from_slice(
                            &mut (*pnode).values,
                            &mut (*centre).values[n_centre..],
                            n_node,
                        );
                        if !(*centre).is_leaf() {
                            let non_centre = (*parent).children[par_idx];
                            for c in (*pnode).children.iter() {
                                if let &Some(x) = c {
                                    (*x.as_ptr()).parent = non_centre;
                                } else {
                                    break;
                                }
                            }
                            copy_from_slice(
                                &mut (*pnode).children,
                                &mut (*centre).children[n_centre..],
                                n_node + 1,
                            );
                        }
                        (*centre).n_keys += n_node;
                        delete_at_slice(&mut (*parent).children, par_idx + 1, (*parent).n_keys + 1);
                        Box::from_raw(pnode);
                        if (*parent).parent.is_none() && (*parent).n_keys == 1 {
                            // delete node
                            (*centre).parent = None;
                            self.root = (*parent).children[0].unwrap();
                            Box::from_raw(parent);
                            break;
                        } else {
                            idx = (*parent).index((&mut *node).into()).unwrap();
                            node = parent;
                        }
                    }
                } else {
                    break; // root node does not need to re-balance
                }
            }
        }
        return true;
    }

    #[inline]
    fn update(&mut self, key: K, val: V) {
        unsafe {
            let mut node = Some(self.root);
            while let Some(ptr) = node {
                let ptr = ptr.as_ptr();
                let idx = (*ptr).posit(&key);
                if (*ptr).keys[idx] == key {
                    write((*ptr).values.as_mut_ptr().add(idx), val);
                    break;
                } else {
                    node = (*ptr).children[idx];
                }
            }
        }
    }

    #[inline]
    fn query(&self, key: K) -> Option<V> {
        unsafe {
            let mut node = Some(self.root);
            while let Some(ptr) = node {
                let ptr = ptr.as_ptr();
                let idx = (*ptr).posit(&key);
                if (*ptr).keys[idx] == key {
                    return Some((*ptr).values[idx].clone());
                } else {
                    node = (*ptr).children[idx];
                }
            }
            None
        }
    }

    #[inline]
    fn where_val<F: FnMut(&V) -> bool>(&self, mut f: F) -> Vec<V> {
        unsafe {
            let mut res = Vec::<V>::with_capacity(self.size);
            let mut stack =
                Vec::<NonNull<BTreeNode<K, V, N>>>::with_capacity(self.size * 2 / (N - 1));
            stack.push(self.root);
            while let Some(node) = stack.pop() {
                let n_keys = (*node.as_ptr()).n_keys;
                for v in (*node.as_ptr()).values[..n_keys].iter() {
                    if f(v) {
                        res.push(v.clone());
                    }
                }
                for c in (*node.as_ptr()).children.iter() {
                    if let &Some(child) = c {
                        stack.push(child)
                    } else {
                        break;
                    }
                }
            }
            res.shrink_to_fit();
            res
        }
    }

    #[inline]
    fn where_key<F: FnMut(&K) -> bool>(&self, mut f: F) -> Vec<K> {
        unsafe {
            let mut res = Vec::<K>::with_capacity(self.size);
            let mut stack =
                Vec::<NonNull<BTreeNode<K, V, N>>>::with_capacity(self.size * 2 / (N - 1));
            stack.push(self.root);
            while let Some(node) = stack.pop() {
                let n_keys = (*node.as_ptr()).n_keys;
                for k in (*node.as_ptr()).keys[..n_keys].iter() {
                    if f(k) {
                        res.push(k.clone());
                    }
                }
                for c in (*node.as_ptr()).children.iter() {
                    if let &Some(child) = c {
                        stack.push(child)
                    } else {
                        break;
                    }
                }
            }
            res.shrink_to_fit();
            res
        }
    }

    #[inline]
    fn to_vector(&self) -> Vec<(K, V)> {
        unsafe {
            let mut res = Vec::<(K, V)>::with_capacity(self.size);
            let mut stack =
                Vec::<NonNull<BTreeNode<K, V, N>>>::with_capacity(self.size * 2 / (N - 1));
            stack.push(self.root);
            while let Some(node) = stack.pop() {
                let n_keys = (*node.as_ptr()).n_keys;
                (*node.as_ptr()).keys[..n_keys]
                    .iter()
                    .zip((*node.as_ptr()).values[..n_keys].iter())
                    .for_each(|(k, v)| res.push((*k, v.clone())));

                for c in (*node.as_ptr()).children.iter() {
                    if let &Some(child) = c {
                        stack.push(child)
                    } else {
                        break;
                    }
                }
            }
            res
        }
    }

    #[inline]
    fn min_key(&self) -> Option<K> {
        unsafe {
            let mut node = self.root;
            while (*node.as_ptr()).n_keys > 0 {
                if let Some(child) = (*node.as_ptr()).children[0] {
                    node = child;
                } else {
                    return Some((*node.as_ptr()).keys[0]);
                }
            }
            None
        }
    }

    #[inline]
    fn min_val(&self) -> Option<K>
    where
        V: Clone + Sized + Ord,
    {
        unsafe {
            let mut key: Option<K> = None;
            let mut min_val: Option<V> = None;
            let mut stack =
                Vec::<NonNull<BTreeNode<K, V, N>>>::with_capacity(self.size * 2 / (N - 1));
            stack.push(self.root);
            while let Some(node) = stack.pop() {
                let n_keys = (*node.as_ptr()).n_keys;
                for (i, v) in (*node.as_ptr()).values[..n_keys].iter().enumerate() {
                    if let Some(ref min) = min_val {
                        if min.gt(v) {
                            min_val = Some(v.clone());
                            key = Some((*node.as_ptr()).keys[i]);
                        }
                    } else {
                        min_val = Some(v.clone());
                        key = Some((*node.as_ptr()).keys[i]);
                    }
                }
                for c in (*node.as_ptr()).children.iter() {
                    if let &Some(child) = c {
                        stack.push(child)
                    } else {
                        break;
                    }
                }
            }
            key
        }
    }

    #[inline]
    fn max_key(&self) -> Option<K> {
        unsafe {
            let mut node = self.root;
            let mut n_keys = (*node.as_ptr()).n_keys;
            while n_keys > 0 {
                if let Some(child) = (*node.as_ptr()).children[n_keys - 1] {
                    node = child;
                    n_keys = (*node.as_ptr()).n_keys;
                } else {
                    return Some((*node.as_ptr()).keys[n_keys - 1]);
                }
            }
            None
        }
    }

    #[inline]
    fn max_val(&self) -> Option<K>
    where
        V: Clone + Sized + Ord,
    {
        unsafe {
            let mut key: Option<K> = None;
            let mut max_val: Option<V> = None;
            let mut stack =
                Vec::<NonNull<BTreeNode<K, V, N>>>::with_capacity(self.size * 2 / (N - 1));
            stack.push(self.root);
            while let Some(node) = stack.pop() {
                let n_keys = (*node.as_ptr()).n_keys;
                for (i, v) in (*node.as_ptr()).values[..n_keys].iter().enumerate() {
                    let value = Some(v.clone());
                    if max_val < value {
                        max_val = value;
                        key = Some((*node.as_ptr()).keys[i]);
                    }
                }
                for c in (*node.as_ptr()).children.iter() {
                    if let &Some(child) = c {
                        stack.push(child)
                    } else {
                        break;
                    }
                }
            }
            key
        }
    }

    #[inline]
    fn clear(&mut self) {
        *self = Self::new();
    }

    #[inline]
    fn size(&self) -> usize {
        self.size
    }
}

struct BPlusNode<K, V, const N: usize> {
    n_keys: usize,
    keys: [K; N],
    parent: Option<NonNull<BPlusNode<K, V, N>>>,
    prev: Option<NonNull<BPlusNode<K, V, N>>>,
    next: Option<NonNull<BPlusNode<K, V, N>>>,
    children: [Option<NonNull<BPlusNode<K, V, N>>>; N],
    values: Vec<V>,
}

trait BPlusNodeBase<K> {
    fn is_leaf(&self) -> bool;
    fn posit(&self, key: &K) -> usize;
}

trait BPlusTreeNode<K>: BPlusNodeBase<K> {
    fn create() -> Box<Self>;
    fn index(&mut self, child: NonNull<Self>) -> Option<usize>;
    fn try_insert(&mut self, key: K, brother: NonNull<Self>) -> bool;
    fn try_delete(&mut self, idx: usize) -> bool;
    fn split_to(&mut self, idx: usize, brother: NonNull<Self>) -> Option<NonNull<Self>>;
    fn combine_with(&mut self, mid: K, other: Box<Self>);
}

trait BPlusLeafNode<K, V>: BPlusNodeBase<K> {
    fn create() -> Box<Self>;
    fn try_insert(&mut self, key: K, val: V) -> bool;
    fn try_delete(&mut self, idx: usize) -> bool;
    fn split_to(&mut self) -> Option<NonNull<Self>>;
    fn combine_with(&mut self, other: Box<Self>);
}

impl<K, V, const N: usize> BPlusNodeBase<K> for BPlusNode<K, V, N>
where
    K: Copy + Ord + Default,
{
    #[inline]
    fn is_leaf(&self) -> bool {
        self.values.capacity() == 0
    }

    #[inline]
    fn posit(&self, key: &K) -> usize {
        let (mut i, mut j) = (0, self.n_keys);
        while i != j {
            match self.keys[(i + j) / 2].cmp(key) {
                Ordering::Less => i = (i + j) / 2 + 1,
                Ordering::Greater => j = (i + j) / 2,
                Ordering::Equal => match self.is_leaf() {
                    true => return (i + j) / 2,
                    false => return (i + j) / 2 + 1,
                },
            }
        }
        i
    }
}

impl<K, V, const N: usize> BPlusTreeNode<K> for BPlusNode<K, V, N>
where
    K: Copy + Ord + Default,
{
    #[inline]
    fn create() -> Box<Self> {
        Box::new(Self {
            n_keys: 0,
            keys: [Default::default(); N],
            parent: None,
            prev: None,
            next: None,
            children: unsafe { zeroed() },
            values: Vec::<V>::with_capacity(0),
        })
    }

    #[inline]
    fn index(&mut self, child: NonNull<Self>) -> Option<usize> {
        self.children
            .iter()
            .enumerate()
            .find_map(|(idx, &c)| match c {
                Some(c) if c == child => Some(idx),
                _ => None,
            })
    }

    #[inline]
    fn try_insert(&mut self, key: K, brother: NonNull<Self>) -> bool {
        let place = self.posit(&key);
        assert!(!self.keys[place].eq(&key), "key exists already");
        unsafe {
            insert_at_slice(&mut self.keys, key, place, self.n_keys);
            if self.n_keys < N {
                insert_at_slice(
                    &mut self.children,
                    Some(brother),
                    place + 1,
                    self.n_keys + 1,
                );
            }
        }
        self.n_keys += 1;
        self.n_keys == N
    }

    #[inline]
    fn split_to(&mut self, idx: usize, mut brother: NonNull<Self>) -> Option<NonNull<Self>> {
        unsafe {
            if self.n_keys == N {
                let mut leaves: Vec<Option<NonNull<BPlusNode<K, V, N>>>> = vec![None; N + 1];
                swap_slices(&mut self.children, &mut leaves, N);
                insert_at_slice(&mut leaves, Some(brother), idx, N);
                self.n_keys = N / 2;
                let mut boxed = Self::create();
                boxed.n_keys = (N - 1) / 2;
                copy_from_slice(&mut self.keys[N / 2 + 1..], &mut boxed.keys, (N - 1) / 2);
                swap_slices(&mut self.children, &mut leaves, N / 2 + 1);
                swap_slices(&mut boxed.children, &mut leaves[N / 2 + 1..], (N + 1) / 2);
                brother = Box::leak(boxed).into();
                for c in (*brother.as_ptr()).children.iter() {
                    if let &Some(x) = c {
                        (*x.as_ptr()).parent = Some(brother);
                    }
                }
                return Some(brother);
            }
        }
        None
    }

    #[inline]
    fn try_delete(&mut self, idx: usize) -> bool {
        unsafe {
            delete_at_slice(&mut self.keys, idx, self.n_keys);
            match idx {
                0 => delete_at_slice(&mut self.children, 0, self.n_keys + 1),
                _ => delete_at_slice(&mut self.children, idx + 1, self.n_keys + 1),
            }
        }
        self.n_keys -= 1;
        self.n_keys < (N - 1) / 2
    }

    #[inline]
    fn combine_with(&mut self, mid: K, mut other: Box<Self>) {
        assert!(
            self.keys[self.n_keys - 1].lt(&mid) && mid.lt(&other.keys[0]),
            "should ascending parameters"
        );
        unsafe {
            insert_at_slice(&mut self.keys, mid, self.n_keys, self.n_keys);
            copy_from_slice(
                &mut other.keys,
                &mut self.keys[self.n_keys + 1..],
                other.n_keys,
            );
            copy_from_slice(
                &mut other.children,
                &mut self.children[self.n_keys + 1..],
                other.n_keys + 1,
            );
        }
        self.n_keys += other.n_keys + 1;
    }
}

impl<K, V, const N: usize> BPlusLeafNode<K, V> for BPlusNode<K, V, N>
where
    K: Copy + Ord + Default,
    V: Clone + Sized,
{
    #[inline]
    fn create() -> Box<Self> {
        Box::new(Self {
            n_keys: 0,
            keys: [Default::default(); N],
            parent: None,
            prev: None,
            next: None,
            children: unsafe { zeroed() },
            values: Vec::<V>::with_capacity(N),
        })
    }

    #[inline]
    fn try_insert(&mut self, key: K, val: V) -> bool {
        let place = self.posit(&key);
        assert!(!self.keys[place].eq(&key), "key exists already");
        unsafe {
            insert_at_slice(&mut self.keys, key, place, self.n_keys);
            insert_at_slice(&mut self.values, val, place, self.n_keys);
        }
        self.n_keys += 1;
        self.n_keys == N
    }

    #[inline]
    fn split_to(&mut self) -> Option<NonNull<Self>> {
        unsafe {
            if self.n_keys == N {
                self.n_keys = N / 2;
                let mut brother = <Self as BPlusLeafNode<K, V>>::create();
                brother.n_keys = (N + 1) / 2;
                copy_from_slice(&mut self.keys[N / 2..], &mut brother.keys, (N + 1) / 2);
                copy_from_slice(&mut self.values[N / 2..], &mut brother.values, (N + 1) / 2);
                brother.prev = Some(self.into());
                brother.parent = self.parent;
                let brother = Box::leak(brother).into();
                if let Some(next) = self.next {
                    (*next.as_ptr()).prev = Some(brother);
                    (*brother.as_ptr()).next = self.next;
                }
                self.next = Some(brother);
                return Some(brother);
            }
        }
        None
    }

    #[inline]
    fn try_delete(&mut self, idx: usize) -> bool {
        unsafe {
            delete_at_slice(&mut self.keys, idx, self.n_keys);
            delete_at_slice(&mut self.values, idx, self.n_keys);
            if idx == 0 && !self.parent.is_none() {
                let par = self.parent.unwrap().as_ptr();
                let par_idx = <Self as BPlusTreeNode<K>>::index(&mut *par, self.into()).unwrap();
                if par_idx > 0 {
                    (*par).keys[par_idx - 1] = self.keys[0];
                }
            }
        }
        self.n_keys -= 1;
        self.n_keys < N / 2
    }

    #[inline]
    fn combine_with(&mut self, mut other: Box<Self>) {
        unsafe {
            copy_from_slice(&mut other.keys, &mut self.keys[self.n_keys..], other.n_keys);
            copy_from_slice(
                &mut other.values,
                &mut self.values[self.n_keys..],
                other.n_keys,
            );
            self.n_keys += other.n_keys;
            self.next = other.next;
            if let Some(next) = other.next {
                (*next.as_ptr()).prev = Some(self.into());
            }
        }
    }
}

pub struct BPlusTree<K, V, const N: usize> {
    size: usize,
    root: NonNull<BPlusNode<K, V, N>>,
    data: NonNull<BPlusNode<K, V, N>>,
}

impl<K, V, const N: usize> BPlusTree<K, V, N>
where
    K: Copy + Ord + Default,
    V: Clone + Sized,
{
    #[inline]
    fn create_leaf_node() -> Box<BPlusNode<K, V, N>> {
        <BPlusNode<K, V, N> as BPlusLeafNode<K, V>>::create()
    }

    #[inline]
    fn load_leaf_node(node: &mut BPlusNode<K, V, N>, keys: &[K], values: &[V]) {
        assert!(keys.len() < N && keys.len() == values.len());
        if node.is_leaf() {
            unsafe {
                node.n_keys = keys.len();
                copy_from_slice(keys, &mut node.keys, node.n_keys);
                copy_from_slice(values, &mut node.values, node.n_keys);
            }
        }
    }

    #[inline]
    fn create_tree_node() -> Box<BPlusNode<K, V, N>> {
        <BPlusNode<K, V, N> as BPlusTreeNode<K>>::create()
    }

    #[inline]
    fn try_insert_to_leaf(node: &mut BPlusNode<K, V, N>, key: K, val: V) -> bool {
        <BPlusNode<K, V, N> as BPlusLeafNode<K, V>>::try_insert(node, key, val)
    }

    #[inline]
    fn try_insert_to_tree(
        node: &mut BPlusNode<K, V, N>,
        key: K,
        brother: NonNull<BPlusNode<K, V, N>>,
    ) -> bool {
        <BPlusNode<K, V, N> as BPlusTreeNode<K>>::try_insert(node, key, brother)
    }

    #[inline]
    fn must_split_leaf(node: &mut BPlusNode<K, V, N>) -> NonNull<BPlusNode<K, V, N>> {
        if let Some(other) = <BPlusNode<K, V, N> as BPlusLeafNode<K, V>>::split_to(node) {
            return other;
        } else {
            panic!("node does not need to split");
        }
    }

    #[inline]
    fn must_split_tree(
        node: &mut BPlusNode<K, V, N>,
        idx: usize,
        brother: NonNull<BPlusNode<K, V, N>>,
    ) -> NonNull<BPlusNode<K, V, N>> {
        if let Some(other) = <BPlusNode<K, V, N> as BPlusTreeNode<K>>::split_to(node, idx, brother)
        {
            return other;
        } else {
            panic!("node does not need to split");
        }
    }

    #[inline]
    fn try_delete_in_leaf(node: &mut BPlusNode<K, V, N>, idx: usize) -> bool {
        <BPlusNode<K, V, N> as BPlusLeafNode<K, V>>::try_delete(node, idx)
    }

    #[inline]
    fn try_delete_in_tree(node: &mut BPlusNode<K, V, N>, idx: usize) -> bool {
        <BPlusNode<K, V, N> as BPlusTreeNode<K>>::try_delete(node, idx)
    }

    #[inline]
    fn combine_leaf(node: &mut BPlusNode<K, V, N>, other: Box<BPlusNode<K, V, N>>) {
        <BPlusNode<K, V, N> as BPlusLeafNode<K, V>>::combine_with(node, other)
    }

    #[inline]
    fn combine_tree(node: &mut BPlusNode<K, V, N>, mid: K, other: Box<BPlusNode<K, V, N>>) {
        <BPlusNode<K, V, N> as BPlusTreeNode<K>>::combine_with(node, mid, other)
    }

    #[inline]
    fn try_borrow_from_leaf(node: NonNull<BPlusNode<K, V, N>>, from_left: bool) -> bool {
        unsafe {
            let node = node.as_ptr();
            let other = match from_left {
                true => (*node).prev,
                false => (*node).next,
            };
            if let Some(o) = other {
                let brother = o.as_ptr();
                if (*brother).parent == (*node).parent && (*brother).n_keys > N / 2 {
                    let elem = from_left as usize * ((*brother).n_keys - 1);
                    let k = (*brother).keys[elem];
                    Self::try_insert_to_leaf(&mut *node, k, (*brother).values[elem].clone());
                    Self::try_delete_in_leaf(&mut *brother, elem);
                    if from_left {
                        if let Some(mut parent) = (*node).parent {
                            let idx = Self::index(parent.as_mut(), o);
                            (*parent.as_ptr()).keys[idx] = k;
                        }
                    }
                    return true;
                }
            }
        }
        false
    }

    #[inline]
    fn try_borrow_from_tree(mut node: NonNull<BPlusNode<K, V, N>>, from_left: bool) -> bool {
        unsafe {
            if let Some(mut parent) = (*node.as_ptr()).parent {
                let idx = Self::index(parent.as_mut(), node);
                let other = match (from_left, idx) {
                    (true, idx) if idx > 0 => (*parent.as_ptr()).children[idx - 1],
                    (false, idx) if idx < N - 1 => (*parent.as_ptr()).children[idx + 1],
                    _ => None,
                };
                if let Some(o) = other {
                    let brother = o.as_ptr();
                    if (*brother).n_keys > (N - 1) / 2 {
                        let k_idx = idx - from_left as usize;
                        let k = (*parent.as_ptr()).keys[k_idx];
                        if from_left {
                            let elem = (*brother).n_keys;
                            Self::try_insert_to_tree(
                                node.as_mut(),
                                k,
                                (*brother).children[elem].unwrap(),
                            );
                            (*parent.as_ptr()).keys[k_idx] = (*brother).keys[elem - 1];
                            Self::try_delete_in_tree(&mut *brother, elem - 1);
                        } else {
                            Self::try_insert_to_tree(
                                node.as_mut(),
                                k,
                                (*brother).children[0].unwrap(),
                            );
                            (*parent.as_ptr()).keys[k_idx] = (*brother).keys[0];
                            Self::try_delete_in_tree(&mut *brother, 0);
                        }
                        return true;
                    }
                }
            }
        }
        false
    }

    #[inline]
    fn index(node: &mut BPlusNode<K, V, N>, child: NonNull<BPlusNode<K, V, N>>) -> usize {
        if let Some(idx) = <BPlusNode<K, V, N> as BPlusTreeNode<K>>::index(node, child) {
            return idx;
        } else {
            panic!("node does not find the child");
        }
    }
}

impl<K, V, const N: usize> BPlusTree<K, V, N>
where
    K: Copy + Ord + Default,
    V: Clone + Sized,
{
    #[inline]
    pub fn bulk_loading(mut keys: Vec<K>, mut values: Vec<V>) -> Self {
        sort_key_values(&mut keys, &mut values);
        let mut node: NonNull<BPlusNode<K, V, N>> = Box::leak(Self::create_leaf_node()).into();
        unsafe {
            if keys.len() < N {
                Self::load_leaf_node(node.as_mut(), &keys, &values);
                Self {
                    size: keys.len(),
                    root: node,
                    data: node,
                }
            } else {
                let mut root = Self::create_tree_node();
                Self::load_leaf_node(node.as_mut(), &keys[..N - 1], &values[..N - 1]);
                root.children[0] = Some(node);
                let mut tree = Self {
                    size: keys.len(),
                    root: Box::leak(root).into(),
                    data: node,
                };
                (*node.as_ptr()).parent = Some(tree.root);
                let mut parent = tree.root;
                for idx in (N - 1..keys.len()).step_by(N - 1) {
                    let mut rhd: NonNull<BPlusNode<K, V, N>> =
                        Box::leak(Self::create_leaf_node()).into();
                    let mut ident = keys[idx];
                    Self::load_leaf_node(
                        rhd.as_mut(),
                        &keys[idx..idx + N - 1],
                        &values[idx..idx + N - 1],
                    );
                    (*rhd.as_ptr()).parent = Some(parent);
                    (*node.as_ptr()).next = Some(rhd);
                    (*rhd.as_ptr()).prev = Some(node);

                    let (mut par, mut child) = (parent.as_ptr(), rhd);
                    while (*par).n_keys == N - 1 {
                        (*par).keys[N - 1] = ident;
                        ident = (*par).keys[N / 2];
                        child = match child == rhd {
                            true => {
                                parent = Self::must_split_tree(&mut *par, N, child);
                                parent
                            }
                            false => Self::must_split_tree(&mut *par, N, child),
                        };
                        par = match (*par).parent {
                            None => {
                                let parn = Box::leak(Self::create_tree_node()).into();
                                (*node.as_ptr()).parent = Some(parn);
                                (*child.as_ptr()).parent = Some(parn);
                                tree.root = parn;
                                parn.as_ptr()
                            }
                            Some(parn) => {
                                (*child.as_ptr()).parent = Some(parn);
                                parn.as_ptr()
                            }
                        };
                    }
                    (*par).keys[(*par).n_keys] = ident;
                    (*par).children[(*par).n_keys + 1] = Some(child);
                    (*par).n_keys += 1;

                    node = rhd;
                }
                tree
            }
        }
    }
}

impl<K, V, const N: usize> SearchTreeBase<K, V> for BPlusTree<K, V, N>
where
    K: Copy + Ord + Default,
    V: Clone + Sized,
{
    #[inline]
    fn new() -> Self {
        let node = Box::leak(Self::create_leaf_node()).into();
        Self {
            size: 0,
            root: node,
            data: node,
        }
    }

    #[inline]
    fn insert(&mut self, key: K, val: V) -> bool {
        unsafe {
            let mut node = self.root;
            while !(*node.as_ptr()).is_leaf() {
                let idx = (*node.as_ptr()).posit(&key);
                if let Some(x) = (*node.as_ptr()).children[idx] {
                    node = x;
                }
            }
            let try_idx = (*node.as_ptr()).posit(&key);
            if (*node.as_ptr()).keys[try_idx].eq(&key) {
                return false;
            }
            if !Self::try_insert_to_leaf(node.as_mut(), key, val) {
                let mut ident = (*node.as_ptr()).keys[N / 2];
                let mut brother = Self::must_split_leaf(node.as_mut());
                loop {
                    node = match (*node.as_ptr()).parent {
                        None => {
                            let par: NonNull<BPlusNode<K, V, N>> =
                                Box::leak(Self::create_tree_node()).into();
                            (*node.as_ptr()).parent = Some(par);
                            (*brother.as_ptr()).parent = Some(par);
                            self.root = par;
                            par
                        }
                        Some(par) => {
                            (*brother.as_ptr()).parent = Some(par);
                            par
                        }
                    };
                    if !Self::try_insert_to_tree(node.as_mut(), ident, brother) {
                        let idx = (*node.as_ptr()).posit(&ident);
                        ident = (*node.as_ptr()).keys[N / 2];
                        brother = Self::must_split_tree(node.as_mut(), idx, brother);
                    } else {
                        break;
                    }
                }
            }
            self.size += 1;
            return true;
        }
    }

    #[inline]
    fn delete(&mut self, key: K) -> bool {
        unsafe {
            let (mut node, mut par_idx) = (self.root, 0);
            while !(*node.as_ptr()).is_leaf() {
                par_idx = (*node.as_ptr()).posit(&key);
                if let Some(x) = (*node.as_ptr()).children[par_idx] {
                    node = x;
                }
            }
            let pnode = node.as_ptr();
            let idx = (*pnode).posit(&key);
            if (*pnode).keys[idx].eq(&key) {
                if !Self::try_delete_in_leaf(node.as_mut(), idx) {
                    if let Some(parent) = (*pnode).parent {
                        // right brother has enough keys
                        if !Self::try_borrow_from_leaf(node, false) {
                            // left brother has enough keys
                            if !Self::try_borrow_from_leaf(node, true) {
                                // combines
                                if par_idx > 0 {
                                    par_idx -= 1;
                                    let mut brother = (*pnode).prev.unwrap();
                                    Self::combine_leaf(brother.as_mut(), Box::from_raw(pnode));
                                } else {
                                    let brother = (*pnode).prev.unwrap().as_ptr();
                                    Self::combine_leaf(node.as_mut(), Box::from_raw(brother));
                                }
                                delete_at_slice(
                                    &mut (*parent.as_ptr()).children,
                                    par_idx + 1,
                                    (*parent.as_ptr()).n_keys + 1,
                                );
                                node = parent;
                                while !Self::try_delete_in_tree(node.as_mut(), par_idx) {
                                    if let Some(mut parent) = (*node.as_ptr()).parent {
                                        par_idx = Self::index(parent.as_mut(), node);
                                        // right brother has enough keys
                                        if Self::try_borrow_from_tree(node, false) {
                                            break;
                                        }
                                        // left brother has enough keys
                                        if Self::try_borrow_from_tree(node, true) {
                                            break;
                                        } else {
                                            // combines
                                            if par_idx > 0 {
                                                par_idx -= 1;
                                                let mut brother =
                                                    (*parent.as_ptr()).children[par_idx].unwrap();
                                                Self::combine_tree(
                                                    brother.as_mut(),
                                                    (*parent.as_ptr()).keys[par_idx],
                                                    Box::from_raw(pnode),
                                                );
                                            } else {
                                                let brother = (*parent.as_ptr()).children
                                                    [par_idx + 1]
                                                    .unwrap();
                                                Self::combine_tree(
                                                    node.as_mut(),
                                                    (*parent.as_ptr()).keys[par_idx],
                                                    Box::from_raw(brother.as_ptr()),
                                                );
                                            }
                                            delete_at_slice(
                                                &mut (*parent.as_ptr()).children,
                                                par_idx + 1,
                                                (*parent.as_ptr()).n_keys + 1,
                                            );
                                            node = parent;
                                        }
                                    } else {
                                        if (*node.as_ptr()).n_keys == 0 {
                                            // delete node
                                            if let Some(child) = (*node.as_ptr()).children[0] {
                                                (*child.as_ptr()).parent = None;
                                                self.root = child;
                                                Box::from_raw(node.as_ptr());
                                            }
                                        }
                                        break;
                                    }
                                }
                            }
                        }
                    }
                }
                self.size -= 1;
                return true;
            } else {
                return false;
            }
        }
    }

    #[inline]
    fn update(&mut self, key: K, val: V) {
        unsafe {
            let mut node = self.root.as_ptr();
            while !(*node).is_leaf() {
                let idx = (*node).posit(&key);
                if let Some(x) = (*node).children[idx] {
                    node = x.as_ptr();
                }
            }
            let idx = (*node).posit(&key);
            if (*node).keys[idx] == key {
                write((*node).values.as_mut_ptr().add(idx), val);
            }
        }
    }

    #[inline]
    fn query(&self, key: K) -> Option<V> {
        unsafe {
            let mut node = self.root.as_ptr();
            while !(*node).is_leaf() {
                let idx = (*node).posit(&key);
                if let Some(x) = (*node).children[idx] {
                    node = x.as_ptr();
                }
            }
            let idx = (*node).posit(&key);
            if (*node).keys[idx] == key {
                Some((*node).values[idx].clone())
            } else {
                None
            }
        }
    }

    #[inline]
    fn where_val<F: FnMut(&V) -> bool>(&self, mut f: F) -> Vec<V> {
        unsafe {
            let mut res = Vec::<V>::with_capacity(self.size);
            let mut node = Some(self.data);
            while let Some(n) = node {
                let n_keys = (*n.as_ptr()).n_keys;
                for v in (*n.as_ptr()).values[..n_keys].iter() {
                    if f(v) {
                        res.push(v.clone());
                    }
                }
                node = (*n.as_ptr()).next;
            }
            res.shrink_to_fit();
            res
        }
    }

    #[inline]
    fn where_key<F: FnMut(&K) -> bool>(&self, mut f: F) -> Vec<K> {
        unsafe {
            let mut res = Vec::<K>::with_capacity(self.size);
            let mut node = Some(self.data);
            while let Some(n) = node {
                let n_keys = (*n.as_ptr()).n_keys;
                for k in (*n.as_ptr()).keys[..n_keys].iter() {
                    if f(k) {
                        res.push(k.clone());
                    }
                }
                node = (*n.as_ptr()).next;
            }
            res.shrink_to_fit();
            res
        }
    }

    #[inline]
    fn to_vector(&self) -> Vec<(K, V)> {
        unsafe {
            let mut res = Vec::<(K, V)>::with_capacity(self.size);
            let mut node = Some(self.data);
            while let Some(n) = node {
                let n_keys = (*n.as_ptr()).n_keys;
                (*n.as_ptr()).keys[..n_keys]
                    .iter()
                    .zip((*n.as_ptr()).values[..n_keys].iter())
                    .for_each(|(k, v)| res.push((*k, v.clone())));
                node = (*n.as_ptr()).next;
            }
            res
        }
    }

    #[inline]
    fn min_key(&self) -> Option<K> {
        unsafe {
            if (*self.data.as_ptr()).n_keys > 0 {
                return Some((*self.data.as_ptr()).keys[0]);
            }
        }
        None
    }

    #[inline]
    fn min_val(&self) -> Option<K>
    where
        V: Clone + Sized + Ord,
    {
        unsafe {
            if (*self.data.as_ptr()).n_keys > 0 {
                let mut key: Option<K> = Some((*self.data.as_ptr()).keys[0]);
                let mut min_val = (*self.data.as_ptr()).values[0].clone();
                let mut node = Some(self.data);
                while let Some(n) = node {
                    let n_keys = (*n.as_ptr()).n_keys;
                    for (i, v) in (*n.as_ptr()).values[..n_keys].iter().enumerate() {
                        if min_val.gt(v) {
                            min_val = v.clone();
                            key = Some((*n.as_ptr()).keys[i]);
                        }
                    }
                    node = (*n.as_ptr()).next;
                }
                key
            } else {
                None
            }
        }
    }

    #[inline]
    fn max_key(&self) -> Option<K> {
        let mut node = self.data;
        unsafe {
            while let Some(next) = (*node.as_ptr()).next {
                node = next;
            }
            if (*node.as_ptr()).n_keys > 0 {
                return Some((*node.as_ptr()).keys[(*node.as_ptr()).n_keys - 1]);
            }
            None
        }
    }

    #[inline]
    fn max_val(&self) -> Option<K>
    where
        V: Clone + Sized + Ord,
    {
        unsafe {
            if (*self.data.as_ptr()).n_keys > 0 {
                let mut key: Option<K> = Some((*self.data.as_ptr()).keys[0]);
                let mut max_val = (*self.data.as_ptr()).values[0].clone();
                let mut node = Some(self.data);
                while let Some(n) = node {
                    let n_keys = (*n.as_ptr()).n_keys;
                    for (i, v) in (*n.as_ptr()).values[..n_keys].iter().enumerate() {
                        if max_val.lt(v) {
                            max_val = v.clone();
                            key = Some((*n.as_ptr()).keys[i]);
                        }
                    }
                    node = (*n.as_ptr()).next;
                }
                key
            } else {
                None
            }
        }
    }

    #[inline]
    fn clear(&mut self) {
        *self = Self::new()
    }

    #[inline]
    fn size(&self) -> usize {
        self.size
    }
}

fn sort_key_values<K, V>(keys: &mut [K], values: &mut [V])
where
    K: Copy + Ord,
    V: Clone + Sized,
{
    assert!(keys.len() == values.len());

    qsort(keys, values, 0, keys.len());

    fn qsort<K, V>(ks: &mut [K], vs: &mut [V], lo: usize, hi: usize)
    where
        K: Copy + Ord,
        V: Clone + Sized,
    {
        if lo < hi {
            let p = unsafe { posit(ks, vs, (lo + hi) / 2, lo, hi) };
            qsort(ks, vs, lo, p - 1);
            qsort(ks, vs, p + 1, hi);
        }
    }

    unsafe fn posit<K, V>(ks: &mut [K], vs: &mut [V], p: usize, lo: usize, hi: usize) -> usize
    where
        K: Copy + Ord,
        V: Clone + Sized,
    {
        swap_in_slice_at(ks, lo, p);
        swap_in_slice_at(vs, lo, p);
        let (mut p, mut j) = (lo, hi);
        while p != j {
            match p < j {
                true => {
                    if ks[p] <= ks[j] {
                        j -= 1;
                    } else {
                        swap_in_slice_at(ks, p, j);
                        swap_in_slice_at(vs, p, j);
                        swap(&mut p, &mut j);
                        j += 1;
                    }
                }
                false => {
                    if ks[p] >= ks[j] {
                        j += 1;
                    } else {
                        swap_in_slice_at(ks, p, j);
                        swap_in_slice_at(vs, p, j);
                        swap(&mut p, &mut j);
                        j -= 1;
                    }
                }
            }
        }
        p
    }
}
